Taburiente/UMD - Slice&Dice

VAST 2009 Challenge
Challenge 2 - Social Network and Geospatial

Authors and Affiliations:

Manuel Freire, University of Maryland, manuel.freire@gmail.com

Tool(s):

• Excel 2007 and NodeXL (v1.0.1.88): graph preprocessing and annotation
• SocialAction (an internal development build): extended with an ad-hoc tool to create filtered subgraphs from a larger graph, and used to inspect candidate subgraphs.
• TIBCO Spotfire (v3.0.0): initial exploration, and reference and geospatial aspects during the pruning phase.

Video: (no video included)

ANSWERS:

MC2.1: Which of the two social structures, A or B, most closely match the scenario you have identified in the data?

B: I found several candidate instances for B, but zero candidates for A.

MC2.2:  Provide the social network structure you have identified as a tab delimitated file. It should contain the employee, one or more handler, any middle folks, and the localized leader with their international contacts. What are the Flitter names of the persons involved? Please identify only key connections (not all single links for example) as well as any other nodes related to the scenario (if any) you may have discovered that were not described in the two scenarios A and B above.

See Flitter.txt

MC2.3:  Characterize the difference between your social network and the closest social structure you selected (A or B). If you include extra nodes please explain how they fit in to your scenario or analysis. 

The chosen network (Inamori as the Employee, Irvin as Fearless Leader, Gibbons, Schrooten, Welling as Handlers) is only one of the several candidates for network topology B. The Handlers have lower degrees than expected: none reaches the 30-to-40 range. However, Irvin is very well communicated internationally, and Inamori has a degree of exactly 40.

No extra nodes have been included. Two other alternatives (starring Rachel or Tadokoro as Fearless Leaders)are described, but they share no nodes with this one.

Details

Candidates were selected using the following algorithm:

• Classify all vertices into Blue (degree in range 27-50), Green (degree = 5), Pink (degree > 100) and White (other degrees). Blue vertices can be Employees or Handlers; Green vertices can be Middlemen. Pink vertices can be Fearless Leaders. Any other vertices are not considered when searching for candidate subgraphs.
• For each Blue vertex, build a subgraph that includes all edges from that vertex to all its Blue neighbors, and all edges from those neighbors to Green vertices, and all edges from those Green vertices to any Pink vertices. Discard the subgraph it less than 3 Blue neighbors in the first step, or no Pink vertex added, or no Pink vertex ends up with a degree of at least 3.
• Inspect the resulting 22 ego-graphs (see the rows of Figure 1).

Figure 1: results of building candidate subgraphs. Each row contains statistics for a single subgraph. The column ODEG stands for Original Degree; DT stands for Destination Type (color of destination); GEN stands for vertex generation (counts of vertices of each color). The tool is still under heavy development, and the subdivision algorithm was hardcoded.

Surprisingly, connections between the Blue vertices within a given subgraph were very scarce (3 or so in the above 22 graphs). One of these edges was helpful in discarding Bourcier as a possible Employee.

Figure 2: Selected network, using Inamori (degree 40, from Koul) as Employee and Irvin (300, Koul) as Fearless Leader, with Welling (28, Koul), Gibbons (28, Koul) and Schrooten (28, Koul) as Handlers. See above algorithm for vertex selection and color coding.

Figure 3: Two close runner-ups in Terekhov's network. Terekhov (degree 39, Prounov) as Employee, and Rachel (349, Kouvnik) or Tadokoro (233, Koul) as Fearless Leader.

In Rachel's network, Sandri, Middleman for Traupe, also communicates with Usdin (which has his own middleman, Jimenez). This is not prohibited according to the problem statement. No direct connections exist between the Rachel's Handlers (Traupe, Usdin, Bini).

Tadokoro would also make a good Fearless Leader. However, Tadokoro only has 7 international contacts, compared with Rachel's 16-17 international contacts, and Irvin's 24.

MC2.4:  How is your hypothesis about the social structure in Part 1 supported by the city locations of Flovania? What part(s), if any, did the role of geographical information play in the social network of part one?

Geographical information was used in the pruning phase, that is, to help decide which of the candidate subgraphs to choose. The Employee and Fearless leader were expected to be in a large city; multiple cities were expected (it would make sense to spread out the network throughout the territory, at least to isolate Handlers from Middlemen); many international contacts, ideally clustered in one or two countries, are a plus.

Irvin has a large amount of international contacts (24 in total, 10 in Otello, 9 in Tulamuk and 5 in Transpasko). All his Handlers are in Koul, as are Inamori and Irvin himself. The Middlemen are separated from the Handlers, in Prounov and Kouvnik. This makes sense as an additional layer of insulation. If the employee works in an embassy, embassies are usually located in major cities - in this case, Koul.

On the other hand, Rachel's network has 17 international contacts (16 if Mesznaros, Middleman, is discounted), with 12 of them in Transpasko. The Handlers are in Pasko, Prounov and Koul, with Middlemen in Koul, Prounov and Transpasko. Both Usdin (Handler) and Jimenez (Middleman) are in Prounov, as is Terekhov (Employee). This is the only case where Handler and Middleman are both in the same city in Rachel's network; the fact that the Employee would also be from the same place is interesting. Meszaros (Middleman) is in Transpasko: an international handler. Since Transpasko is the main source of Rachel’s international contacts, this seems plausible.

Tadokoro's network was discarded because of a low number of international contacts.

MC2.5:  In general, how are the Flitter users dispersed throughout the cities of this challenge? Which of the surrounding countries may have ties to this criminal operation?  Why might some be of more significant concern than others?,

Most of the 6000 users are from Koul (1998 users) and Prounov (1707). Kouvnik (798) is the third-largest, and Kannvik (320) the fourth; all others are between 100 and 200-odd. This includes the foreign cities of Transpasko (126), Otello (147) and Tulamuk (123).

The International Contacts of Fearless Leader Irvin are mainly from Posana-Otello (10) and Trium-Tulamuk (9). These two countries could be more significant than Transak-Transpasko, with only 5 contacts, mostly with small degree.